package com.xyj.review;

import java.util.Arrays;

/**
 * 数组归并排序
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/9
 */
public class T1 {

    // 归并排序
    // 递归  将数组分为两个，然后排序。

    public static void main(String[] args) {
        int[] nums = {1, 22, 6, 8, 9,};
        sort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
       public static void sort(int[] arr,int left,int right){

           if (left==right){
               return ;
           }
           int mid=left+((right-left)>>1);
           sort(arr,left,mid);
           sort(arr,mid+1,right);
           mergeSort(arr,left,mid,right);
       }

    private static void mergeSort(int[] arr, int left, int mid, int right) {

           //准备一个help数组存放排序后的数
        int[] help = new int[right-left+1];
        int i=0;
        int p=left;
        int q=mid+1;
        //从左到右的看 小的放入数组中
        while (p<=mid&&q<=right){
            help[i++]= arr[p]>arr[q] ? arr[q++]:arr[p++];
        }
        //要么左边数组没了
        while (q<=right){
            help[i++]=arr[q++];
        }
        //要么右边数组没了
        while (p<=mid){
            help[i++]=arr[p++];
        }
        //数组copy
        for (int i1 = 0; i1 < help.length; i1++) {
            arr[left+i1]=help[i1];
        }
    }
}
